class Solution:
    MAX_INT = 10001

    def superEggDrop(self, k: int, n: int) -> int:
        # 定义状态矩阵：dp[i][j] = i层楼，有j个蛋需要的最小次数
        dp = [[0] * (k + 1) for _ in range(n + 1)]

        # 状态转移
        for i1 in range(1, n + 1):
            # 当没有蛋时：无法得出结果
            dp[i1][0] = self.MAX_INT

            # 蛋只有1个时：只能从下往上一层一层试
            dp[i1][1] = i1

            # 计算支持朴素二分所需要的蛋数
            bisect_need = (i1 - 1).bit_length() + 1

            # 蛋既多于1个，又不支持朴素二分时：寻找最优解
            i2 = 1  # dp[i1][j] = max(dp[i2-1][j]+dp[i1-i2][j-1])+1
            for j in range(2, min(bisect_need, k + 1)):
                n1 = dp[i2 - 1][j]
                n2 = dp[i1 - i2][j]
                dp[i1][j] = max(n1, n2) + 1

            # 蛋的数量支持朴素二分时：直接每一次二分寻找结果
            if bisect_need < k + 1:
                dp[i1][bisect_need:] = [bisect_need] * (k + 1 - bisect_need)

            print(i1, bisect_need, ":", dp[i1])


if __name__ == "__main__":
    print(Solution().superEggDrop(1, 2))  # 2
    print(Solution().superEggDrop(2, 6))  # 3
    print(Solution().superEggDrop(3, 14))  # 4

    # 自制用例
    print(Solution().superEggDrop(1, 1))  # 1
    print(Solution().superEggDrop(3, 15))  # 5
